package com.itheima.algorithm.sort;

import java.util.Arrays;

// 计数排序（只处理>0的元素）
public class CountingSortPositive {
    public static void main(String[] args) {
        int[] a = {5,1,1,3,0};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }

    public static void sort(int[] a){
        //1.找到最大值，创建一个最大值+1的count数组
        int max = a[0];
        for(int i=0;i<a.length;i++){
            if(a[i]>max){
                max=a[i];
            }
        }
        // count数组的下标代表待排序元素，count[v]表示待排序元素出现次数
        int[] count = new int[max+1];
        for (int v:a){
            count[v]++;
        }
        int k = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i]>0){
                a[k++]=i;
                count[i]--;
            }
        }
    }
}
